function maopao (array) {
  let arr = array.concat()

  if (arr.length <= 1) return arr

  for (var i = 0; i < arr.length - 1; i++) {
    var isSort = true

    for (var j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        let tmp = arr[j]

        arr[j] = arr[j+1]
        arr[j+1] = tmp
        isSort = false
      }
    }

    if (isSort) break
  }

  return arr
}

function xuanzhe (array) {
  let arr = array.concat()

  if (arr.length <= 1) return arr

  for (let i = 0; i < arr.length - 1; i++) {
    let index = i
    let min = arr[index]

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < min) {
        min = arr[j]
        index = j
      }
    }

    if (index !== i) {
      let tmp = arr[i]

      arr[i] = arr[index]
      arr[index] = tmp
    }
  }

  return arr
}

function charu (array) {
  let arr = array.concat()

  if (arr.length <= 1) return arr

  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j >= 0; j--) {
      if (arr[j] < arr[j-1]) {
        let tmp = arr[j-1]
        arr[j-1] = arr[j]
        arr[j] = tmp
      } else {
        break
      }
    }
  }

  return arr
}

function guibin (array) {
  let arr = array.concat()

  if (arr.length <= 1) return arr

  function _sort (left, right) {
    let rel = []
    let _left = left.concat()
    let _right = right.concat()

    while (_left.length && _right.length) {
      if (_left[0] < _right[0]) {
        rel.push(_left.shift())
      } else {
        rel.push(_right.shift())
      }
    }

    rel = rel.concat(_left, _right)

    return rel
  }

  function _group (array) {
    if (array.length > 1) {
      let index = Math.ceil(array.length / 2)

      return _sort(_group(array.slice(0, index)), _group(array.slice(index)))
    } else {
      return array
    }
  }

  return _group(arr)
}

function kuaipai (array) {
  let arr = array.concat()

  if (arr.length <= 1) return arr

  function _sort (array) {
    if (array.length <= 1) return array

    let baseIndex = 0
    let base = array[baseIndex]
    let left = []
    let right = []

    for (let i = 0; i < array.length; i++) {
      if (i === baseIndex) continue

      if (array[i] <= base) {
        left.push(array[i])
      } else {
        right.push(array[i])
      }
    }

    return [].concat(_sort(left), base, _sort(right))
  }

  return _sort(arr)
}

let nums = []

for (var i = 0; i < 15; i++) {
  nums.push(Math.floor(Math.random() * 1000))
}

let prevTime = 0
let endTime = 0
let li = []

// console.log(`初始化nums: `, nums);

// prevTime = new Date().getTime()
// li = maopao(nums)
// console.log('冒泡排序后');
// // console.log(li)
// endTime = new Date().getTime()
// console.log('运算时间: ', endTime - prevTime, 'ms')

// prevTime = new Date().getTime()
// li = xuanzhe(nums)
// console.log('选择排序后');
// // console.log(li)
// endTime = new Date().getTime()
// console.log('运算时间: ', endTime - prevTime, 'ms')

// prevTime = new Date().getTime()
// li = charu(nums)
// console.log('插入排序后');
// // console.log(li)
// endTime = new Date().getTime()
// console.log('运算时间: ', endTime - prevTime, 'ms')

prevTime = new Date().getTime()
li = guibin(nums)
console.log('归并排序后');
console.log(li)
endTime = new Date().getTime()
console.log('运算时间: ', endTime - prevTime, 'ms')

prevTime = new Date().getTime()
li = kuaipai(nums)
console.log('快速排序后');
console.log(li)
endTime = new Date().getTime()
console.log('运算时间: ', endTime - prevTime, 'ms')